/*rtree.cpp
  this file implements the RTree class*/
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include "rtree.h"
#include "entry.h"
#include "rtnode.h"
#include "../blockfile/cache.h"
#include "../blockfile/blk_file.h"
#include "../linlist/linlist.h"
//------------------------------------------------------------
int sort_dim;  //for use in STR_sort
//------------------------------------------------------------
RTree::RTree(char *fname, Cache *c)
  //use this constructor to restore a tree from an index file
{
    file = new BlockFile(fname, 0);
    cache =c;

    re_data_cands = new LinList();
	deletelist = new LinList();

    char *header = new char [file->get_blocklength()];
    file -> read_header(header);
    read_header(header);
	delete [] header;

    root_ptr = NULL;
}

/*****************************************************************
Use this function to construct a new empty TPR-tree 

tfname: the tree file
b_len: the block length
c: the cache
T: the tree is optimized in [0, T]
dimension: dimensionality

*****************************************************************/

RTree::RTree(char *_tfname, int _blen, Cache *_c, float _T, int _dimension)
{
	//init files--------------------------------------------------
    file=new BlockFile(_tfname, _blen);
    cache=_c;
	//init necessary variables------------------------------------
	re_data_cands=new LinList();   //to be destroyed in desctructor
	deletelist=new LinList();	   //to be destroyed in desctructor

    char *header=new char [file->get_blocklength()];
    read_header(header);
	delete []header;

	T=_T;
    dimension=_dimension;
    root=0;
    root_ptr=NULL;
    root_is_data=true;
    num_of_data=num_of_inodes=num_of_dnodes=0;
	//init the first node-----------------------------------------
    root_ptr = new RTNode(this);
    root_ptr -> level = 0;
    root = root_ptr->block;
	delete root_ptr;
	root_ptr=NULL;
	//------------------------------------------------------------
}


/*****************************************************************
Use this function to construct a new TPR-tree from a dataset
para:

dsfname: the dataset file
tfname: the tree file
b_len: the block length
c: the cache
T: the tree is optimized in [0, T]
dimension: dimensionality

*****************************************************************/

struct MovingObject
{
	bool active;
	float mbr[4];
	float vbr[4];
	float ref;		//reference time
};

RTree::RTree(char *_dsfname, char *_tfname, int _blen, Cache *_c, float _T, int _dimension)
  // construct new R-tree from a specified input textfile with rectangles
{
	int i;
	//init files--------------------------------------------------
    file=new BlockFile(_tfname, _blen);
    cache=_c;
	//init necessary variables------------------------------------
	re_data_cands=new LinList();   //to be destroyed in desctructor
	deletelist=new LinList();	   //to be destroyed in desctructor

    char *header=new char [file->get_blocklength()];
    read_header(header);
	delete []header;

	time=0;
	T=_T;
    dimension=_dimension;
    root=0;
    root_ptr=NULL;
    root_is_data=true;
    num_of_data=num_of_inodes=num_of_dnodes=0;
	//init the first node-----------------------------------------
    root_ptr = new RTNode(this);
    num_of_dnodes++;
    root_ptr -> level = 0;
    root = root_ptr->block;
	//------------------------------------------------------------
	//Get objects from data file one by one
	int maxN=150000;
	//use array of objects is convenient for checking the existence of an object in tree when inserting
	MovingObject *data=new MovingObject[maxN];
	for (int i=0; i<maxN; i++)
		data[i].active=false;

	int record_count = 0;
	FILE *fp;
    if((fp = fopen(_dsfname,"r")) == NULL)
    {
		delete this;
		error("Cannot open R-Tree text file", TRUE);
    }
    else
    {
		Entry *tmpe=new Entry(dimension, this);
		while (!feof(fp))
		{
			record_count ++;
			//init the entry--------------------------------------
			float this_time;
			Entry *d = new Entry(dimension, NULL);
			fscanf(fp, "%d", &(d -> son));
			for (int i = 0; i < 2 * dimension; i ++)
				fscanf(fp, " %f", &(d -> bounces[i]));
			for (i = 0; i < 2*dimension; i ++)
				fscanf(fp, " %f", &(d->velocity[i]));
			fscanf(fp, " %f\n", &this_time);
			if (this_time<time)
				error("\ncannot insert backward in time!\n", true);
			time=this_time;

			d->level=0;
			//----------------------------------------------------
			if (d->son>=maxN)
				error("please increase maxN\n", true);
			if (data[d->son].active) //if this object also exists in this tree, copy data to tmpe in order to delete this node in the tree
			{
				tmpe->son=d->son;
				memcpy(tmpe->bounces, data[d->son].mbr, sizeof(float)*4);
				memcpy(tmpe->velocity, data[d->son].vbr, sizeof(float)*4);
				future_mbr(tmpe->bounces, tmpe->velocity, time-data[d->son].ref, dimension);
				delete_entry(tmpe);
			}
			memcpy(data[d->son].mbr, d->bounces, sizeof(float)*4);
			memcpy(data[d->son].vbr, d->velocity, sizeof(float)*4);
			data[d->son].ref=time;
			data[d->son].active=true;

			insert(d);	//d will be deleted in insert()
			//----------------------------------------------------
			if (record_count % 100 == 0)
			{
				for (int i = 0; i < 79; i ++)  //clear a line
					printf("\b");
				printf("inserting object %d at time %.3f", record_count, time);
			}
			//----------------------------------------------------
		}
		delete tmpe;
    }

	fclose(fp);
	delete [] data;

	printf("\n");
	delete root_ptr;
	root_ptr = NULL;
}
//------------------------------------------------------------
RTree::~RTree()
{
	char *header = new char[file -> get_blocklength()];
    write_header(header);
    file->set_header(header);
    delete [] header;

    if (root_ptr != NULL)
    {
        delete root_ptr;
        root_ptr = NULL;
    }

	if (cache)
      cache -> flush();

    delete file;

    delete re_data_cands;
	delete deletelist;

    printf("This R-Tree contains %d internal, %d data nodes and %d data\n",
	   num_of_inodes, num_of_dnodes, num_of_data);
}
//------------------------------------------------------------
void RTree::del_root()
{
	delete root_ptr;
	root_ptr = NULL;
}
//------------------------------------------------------------
bool RTree::FindLeaf(Entry *_q)
{
	past_mbr(_q->bounces, _q->velocity, time, 2);
	load_root();
	bool cret=root_ptr -> FindLeaf(_q);
	printf("\n");
	del_root();
	return cret;
}

/*****************************************************************
Use this function to insert an entry into the TPR-tree
para:
d: the entry to be inserted

*****************************************************************/

void RTree::insert(Entry* d)
{
	//if d is an entry of a leaf node
	if (d->level==0)
		num_of_data++;
	//set pointer (root_ptr) to the root node 
	load_root();
	//initiate re_lever array
	re_level = new bool[root_ptr -> level + 1];
    for (int i = 0; i <= root_ptr -> level; i++)
        re_level[i] = FALSE;

    //insert d into re_data_cands as the first entry to insert----
    //make a copy of d because it should be erased later
    Linkable *new_link;
	new_link=d->gen_Linkable();
	new_link->level=d->level;
	re_data_cands->insert(new_link);
	delete d;  //follow the convention that the entry will be deleted when insertion finishes
	//------------------------------------------------------------
	//insert an entry

	R_OVERFLOW split_root;
	RTNode *sn; //split node-the point to the new node (if created)
    while (re_data_cands->get_num()>0)
    {
	    Linkable *d_cand;
		d_cand = re_data_cands -> get_first();
        if (d_cand != NULL)
        {
			//copy the first entry from re_data_cands-------------
			Entry *dc=new Entry(dimension, NULL); //the entry to be inserted
            dc->set_from_Linkable(d_cand);
            re_data_cands -> erase();
			//then insert it--------------------------------------
			split_root = root_ptr -> insert(dc, &sn);
			//----------------------------------------------------
        }
        else
	        error("RTree::insert--inconsistent list re_data_cands", true);
	//-------------------------------------------------------------------
	// in case root node spliting occured, root node has to be split
    	if (split_root == SPLIT)
    		// insert will lead to a new root with two sons (i.e. root and sn)
    	{
    	    RTNode *nroot_ptr = new RTNode(this);
    	    nroot_ptr -> level = root_ptr -> level + 1;
    	    num_of_inodes++;
    	    int nroot = nroot_ptr -> block; //this is the block id of the new root

			//now create the first entry of the new root----------
    	    Entry *de = new Entry(dimension, this);
    	    float *nmbr = root_ptr -> get_mbr();
			float *vbr = root_ptr -> get_vmbr(nmbr);
//			past_mbr(nmbr, vbr, time, dimension);
			memcpy(de->bounces, nmbr, 2*dimension*sizeof(float));
			memcpy(de -> velocity, vbr, 2 * dimension * sizeof(float));
    	    delete [] nmbr; delete [] vbr;

    	    de->son = root_ptr->block;
    	    de->son_ptr = NULL;
    	    nroot_ptr -> enter(de);
			delete root_ptr;
			//then the second entry-------------------------------
			de = new Entry(dimension, this);
    	    nmbr = sn -> get_mbr();
			vbr=sn->get_vmbr(nmbr);
//			past_mbr(nmbr, vbr, time, dimension);
    	    memcpy(de -> bounces, nmbr, 2*dimension*sizeof(float));
			memcpy(de -> velocity, vbr, 2 * dimension * sizeof(float));
    	    delete [] nmbr; delete []vbr;

    	    de -> son = sn -> block;
    	    de -> son_ptr = NULL;
    	    nroot_ptr->enter(de);
			delete sn;
			//----------------------------------------------------
    	    root=nroot;
            root_ptr=nroot_ptr;
            root_is_data = FALSE;
        }
    }

    delete [] re_level;
	delete root_ptr;
	root_ptr = NULL;
}
//------------------------------------------------------------
void RTree::load_root()
{
    if (root_ptr == NULL)
        root_ptr = new RTNode(this, root);
}
//------------------------------------------------------------
void RTree::rangeQuery(Entry *_q, float _st, float _ed, int& _rsltcnt)
//void RTree::rangeQuery(Entry *_q, float _st, float _ed, SortedLinList *res)
{
	_st+=time; _ed+=time;
	past_mbr(_q->bounces, _q->velocity, _st, 2);
    load_root();
//  root_ptr -> rangeQuery(_q, _st, _ed, res);
	root_ptr -> rangeQuery(_q, _st, _ed, _rsltcnt);
	delete root_ptr;
	root_ptr = NULL;
}
//------------------------------------------------------------
void RTree::read_header(char *buffer)
{
    int i;

    memcpy(&dimension, buffer, sizeof(dimension));
    i = sizeof(dimension);

    memcpy(&num_of_data, &buffer[i], sizeof(num_of_data));
    i += sizeof(num_of_data);

    memcpy(&num_of_dnodes, &buffer[i], sizeof(num_of_dnodes));
    i += sizeof(num_of_dnodes);

    memcpy(&num_of_inodes, &buffer[i], sizeof(num_of_inodes));
    i += sizeof(num_of_inodes);

    memcpy(&root_is_data, &buffer[i], sizeof(root_is_data));
    i += sizeof(root_is_data);

    memcpy(&root, &buffer[i], sizeof(root));
    i += sizeof(root);

	memcpy(&T, &buffer[i], sizeof(T));
	i += sizeof(T);

	memcpy(&time, &buffer[i], sizeof(float));
	i+=sizeof(time);
}
//------------------------------------------------------------
void RTree::write_header(char *buffer)
{
    int i;

    memcpy(buffer, &dimension, sizeof(dimension));
    i = sizeof(dimension);

    memcpy(&buffer[i], &num_of_data, sizeof(num_of_data));
    i += sizeof(num_of_data);

    memcpy(&buffer[i], &num_of_dnodes, sizeof(num_of_dnodes));
    i += sizeof(num_of_dnodes);

    memcpy(&buffer[i], &num_of_inodes, sizeof(num_of_inodes));
    i += sizeof(num_of_inodes);

    memcpy(&buffer[i], &root_is_data, sizeof(root_is_data));
    i += sizeof(root_is_data);

    memcpy(&buffer[i], &root, sizeof(root));
    i += sizeof(root);

	memcpy(&buffer[i], &T, sizeof(T));
	i += sizeof(T);

	memcpy(&buffer[i], &time, sizeof(float));
	i+=sizeof(time);
}


/*****************************************************************
This function will detect whether two moving regions will intersect
during [st,ed].  If yes, an array containing the intersection interval
will be returned.  

para:
e1: the first moving region
e2: the 2nd one
st: the starting time of the query interval
ed: the ending time

*****************************************************************/

float *RTree::moving_sect(Entry *_e1, Entry *_e2, float _st, float _ed)
{
	int i;
	//first copy the two input entries-------------------------
	Entry *e1=new Entry(dimension, NULL);
	Entry *e2=new Entry(dimension, NULL);
	*e1=*_e1; *e2=*_e2; 
	//set e1.mbr and e2.mbr at time st ---------------------------
	//note the current time is 0
	for (int i=0; i<2*dimension; i++)
	{
		e1->bounces[i]+=e1->velocity[i]*_st;
		e2->bounces[i]+=e2->velocity[i]*_st;
	}
	//init another 2 entries and set their mbrs at ed ------------
	Entry *ee1=new Entry(dimension, NULL);
	Entry *ee2=new Entry(dimension, NULL);
	*ee1=*_e1; *ee2=*_e2; 
	for (i=0; i<2*dimension; i++)
	{
		ee1->bounces[i]+=ee1->velocity[i]*_ed;
		ee2->bounces[i]+=ee2->velocity[i]*_ed;
	}

	float *finalintv=new float[2]; //the final intersection interval
	float curintv[2]; //the intersection interval along the dimension being considered
	
	for (i=0;i<dimension;i++)
	{
		if (e1->bounces[2*i]>e2->bounces[2*i+1] && ee1->bounces[2*i]>ee2->bounces[2*i+1])
		{
			delete [] finalintv;
			delete e1; delete e2; 
			delete ee1; delete ee2;
			return NULL;
		}
		if (e1->bounces[2*i+1]<e2->bounces[2*i] && ee1->bounces[2*i+1]<ee2->bounces[2*i])
        {
			delete [] finalintv; 
			delete e1; delete e2; 
			delete ee1; delete ee2;
			return NULL;
		}

		float A,B,C,D;
		A=e2->bounces[2*i+1]-e1->bounces[2*i];
		B=e1->velocity[2*i]-e2->velocity[2*i+1];
		C=e2->bounces[2*i]-e1->bounces[2*i+1];
		D=e1->velocity[2*i+1]-e2->velocity[2*i];

		if (e1->bounces[2*i]>e2->bounces[2*i+1])
		{
			curintv[0]=_st+A/B;
		}
		else if (e1->bounces[2*i+1]<e2->bounces[2*i])
		{
			curintv[0]=_st+C/D;
		}
		else
			curintv[0]=_st;
//if (curintv[0]<_st)
//printf("testing...caught an error in querying\n");

		if (ee1->bounces[2*i]>ee2->bounces[2*i+1])
		{
			curintv[1]=_st+A/B;
		}
		else if (ee1->bounces[2*i+1]<ee2->bounces[2*i])
		{ 
			curintv[1]=_st+C/D;
		}
		else
			curintv[1]=_ed;
//if (curintv[1]>_ed)
//printf("testing...caught an error in querying\n");

		if (i==0)
		{
			finalintv[0]=curintv[0];
			finalintv[1]=curintv[1];
		}
		else
		{
			if (curintv[0]>finalintv[1] || curintv[1]<finalintv[0])
			{
				delete []finalintv; 
				delete e1; delete e2; 
				delete ee1; delete ee2;
				return NULL;
			}

			if (finalintv[0]<curintv[0])
				finalintv[0]=curintv[0];
			if (finalintv[1]>curintv[1])
				finalintv[1]=curintv[1];
		}
	}
	
	delete e1; delete e2; 
	delete ee1; delete ee2;
	return finalintv;
}

/*****************************************************************
this function adjusts the mbr according to a vmbr to time 0
para:
mbr: the mbr at _time
vbr: the vbr
time: the current time
dim: dimensionality
*****************************************************************/

void past_mbr(float *_mbr, float *_vbr, float _time, int _dim)
{
	for (int i=0; i<2*_dim; i++)
		_mbr[i]=_mbr[i]-_vbr[i]*_time;
}

/*****************************************************************
this function deletes an entry from the current tree
para:
olde: the entry to be inserted --need its mbr at the current time set
*****************************************************************/

void RTree::delete_entry(Entry *_olde)
{
	load_root();
	R_DELETE cret=root_ptr->delete_entry(_olde);
	//del_root();
	//if (cret==ERASED)
	//	error("handle root underflow\n", true); //0907
	if (cret==ERASED)
	{
		if (root_ptr->level>0)
		{
			root=root_ptr->entries[0].son;
		}
	}
	del_root();


	if (cret==NOTFOUND)
	{
		printf("\n could not find entry id=%d at t= %i\n", _olde->son, time);
		printf("mbr=[%f, %f][%f, %f]\n", _olde->bounces[0], _olde->bounces[1],
			_olde->bounces[2], _olde->bounces[3]);
		error("entry not found\n", true);
	}

	num_of_data--;

	while (deletelist->get_num()>0)
	{
		//if (deletelist->get_num()==20)
		//	printf("abc");
		Linkable *d_cand;
		d_cand = deletelist -> get_first();
		if (d_cand != NULL)
		{
			Entry *dc=new Entry(dimension, NULL); //the entry to be inserted
			dc->set_from_Linkable(d_cand);
			deletelist->erase();	
			if (dc->level==0)
				num_of_data--;
			insert(dc);
		}
	}
}

